package com.suanfa;

public class DiGui
{

    /*
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * */
    public static int JumpFloorII(int n)
    {
        //f(1)=1,f(2)=2,f(3)=3,f(4)=5
        if (n <= 3) return 3;
        int pre1 = 1, pre2 = 2;
        int jump = 0;
        for (int i = 3; i <= n; i++)
        {
            jump = pre1 + pre2;
            pre1 = pre2;
            pre2 = jump;
        }
        return jump;

    }

    /*
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * */

    public static int JumpFloorII2(int n)
    {
        //f(1)=1,f(2)=2,f(3)=4,f(4)=8
        return 1 << (n - 1);
    }


    /*
    * 大家都知道斐波那契数列，现在要求输入一个整数n，
    * 请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
      0,1,1,2,3,5.....(n≤39)
    * */
    public static int Fibonacci(int n)
    {
        if (n <= 1) return n;
        //第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项
        int pre1 = 0;
        int pre2 = 1;
        int fib = 0;
        for (int i = 2; i <= n; i++)
        {
            fib = pre1 + pre2;
            pre1 = pre2;
            pre2 = fib;
        }
        return fib;
    }

//    public int Fibonacci(int n)
//    {
//        int a=0;
//        int b=1;
//        for(int i=0;i<n;i++)
//        {
//            b=a+b;
//            a=b-a;
//        }
//        return a;
//
//    }

    /*
     * 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。
     * 请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？
     *
     * */
    public static int RectCover(int n)
    {
        //f(1)=1,f(2)=2,f(3)=3,f(4)=5
        if (n <= 3) return n;
        int pre1 = 1, pre2 = 2;
        int rect = 0;
        for (int i = 3; i <= n; i++)
        {
            rect = pre1 + pre2;
            pre1 = pre2;
            pre2 = rect;
        }
        return rect;
    }


}
